package com.LeeCode;

/**
 * 分割数组的最大值
 */

public class Code410 {
    public static void main(String[] args) {
        int[] nums = {7, 2, 5, 10, 8};
        int k = 2;
        System.out.println(new Code410().splitArray(nums, k));

    }

    public int splitArray(int[] nums, int k) {
        int left = 0, right = 0;

        // 找到二分查找的左右边界
        for (int num : nums) {
            left = Math.max(left, num - 1);
            right += num;
        }

        // 二分查找
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;

            // 判断是否可以将数组分成 ≤k 个子数组，每个子数组的和 ≤ mid
            if (canSplit(nums, k, mid)) {
                // 可以，尝试更小的值
                right = mid;
            } else {
                // 不可以，需要更大的值
                left = mid;
            }
        }

        return right;
    }

    // 判断能否将数组分成 ≤ m 个子数组，每个子数组的和不超过 limit
    private boolean canSplit(int[] nums, int m, int limit) {
        int count = 1;  // 至少是一个子数组
        int curSum = 0;

        for (int num : nums) {
            if (curSum + num > limit) {
                count++;         // 需要新开一个子数组
                curSum = num;    // 当前子数组从当前数字开始
                if (count > m) {
                    return false; // 子数组数量超出限制
                }
            } else {
                curSum += num;
            }
        }

        return count <= m;
    }
}
